/**
 * 顺序队列实现（循环队列）
 * 使用数组实现队列
 */
public class ArrayQueue<T> implements QueueInterface<T> {
    private Object[] queueArray; // 存储队列元素的数组
    private int front; // 队头指针
    private int rear; // 队尾指针
    private int capacity; // 队列容量
    private int count; // 当前元素个数

    /**
     * 构造方法：指定队列初始容量
     * 
     * @param capacity 初始容量
     */
    public ArrayQueue(int capacity) {
        this.capacity = capacity + 1; // 多分配一个位置用于判断队列满
        this.queueArray = new Object[this.capacity];
        this.front = 0;
        this.rear = 0;
        this.count = 0;
    }

    /**
     * 默认构造方法：容量为100
     */
    public ArrayQueue() {
        this(100);
    }

    @Override
    public boolean isEmpty() {
        return front == rear;
    }

    @Override
    public boolean isFull() {
        return (rear + 1) % capacity == front;
    }

    @Override
    public boolean enqueue(T data) {
        if (isFull()) {
            // 扩展容量
            expandCapacity();
        }
        queueArray[rear] = data;
        rear = (rear + 1) % capacity;
        count++;
        return true;
    }

    /**
     * 扩展数组容量
     */
    private void expandCapacity() {
        int newCapacity = capacity * 2;
        Object[] newArray = new Object[newCapacity];

        // 将原队列元素复制到新数组
        int i = 0;
        while (!isEmpty()) {
            newArray[i++] = dequeue();
        }

        queueArray = newArray;
        capacity = newCapacity;
        front = 0;
        rear = i;
        count = i;
    }

    @Override
    @SuppressWarnings("unchecked")
    public T dequeue() {
        if (isEmpty()) {
            throw new RuntimeException("队列为空，无法执行dequeue操作");
        }
        T data = (T) queueArray[front];
        queueArray[front] = null; // 帮助GC
        front = (front + 1) % capacity;
        count--;
        return data;
    }

    @Override
    @SuppressWarnings("unchecked")
    public T peek() {
        if (isEmpty()) {
            throw new RuntimeException("队列为空，无法执行peek操作");
        }
        return (T) queueArray[front];
    }

    @Override
    public int size() {
        return count;
    }

    @Override
    public void clear() {
        front = 0;
        rear = 0;
        count = 0;
        // 可选：清空数组元素帮助GC
        for (int i = 0; i < capacity; i++) {
            queueArray[i] = null;
        }
    }
}
